﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Compression
{
    public class HuffmanTreeBuilder1
    {
        protected readonly Func<string, double, HuffmanTree> _createHuffmanTree;

        public HuffmanTreeBuilder1( Func<string, double, HuffmanTree> createHuffmanTree = null)
        {
            _createHuffmanTree = createHuffmanTree ??
                                ((symbol, freq) => new HuffmanTree(symbol, freq));
        }

        public virtual HuffmanTree BuildTree(IMap<string,double> freq)
        {
            var T = freq.Select(kv => _createHuffmanTree(kv.Key,kv.Value)).ToAlgoritmiaList();

            while ( T.Count > 1)
            {
                var leftTree = T.ArgMin(hfn => hfn.Frequency);
                T.Remove(leftTree);
                var rightTree = T.ArgMin(hfn => hfn.Frequency);
                T.Remove(rightTree);
                var newTree = _createHuffmanTree("", leftTree.Frequency + rightTree.Frequency);
                newTree.AppendLeft(leftTree);
                newTree.AppendRight(rightTree);
                T.Add(newTree);
            }
            return T[0];
        }
    }

 
}
